//给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 
//
// 
//
// 示例 1: 
//
// 输入: [1,2,0]
//输出: 3
// 
//
// 示例 2: 
//
// 输入: [3,4,-1,1]
//输出: 2
// 
//
// 示例 3: 
//
// 输入: [7,8,9,11,12]
//输出: 1
// 
//
// 
//
// 提示： 
//
// 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。 
// Related Topics 数组 
// 👍 745 👎 0

package leetcode.editor.cn;

//Java：缺失的第一个正数
public class P41FirstMissingPositive {

    /**
     *
     * 思路：这道题又是网上的解法.
     *      首先，将数字放在下标对应的位置，比如  -1,3,4,5,6,1  ,1 放在 nums[1],3放在nums[3],以此类推，负数或大于长度的就不管， 结果为 -1,1,6,3,4,5
     *      然后，从第一位开始遍历，1对应nums[1]，6 对应 nums[2]，下标不符，所以结果就是2，如果都符合，判断第0位是不是等于最后一位+1，就能得出结果
     *
     * 执行用时： 1 ms , 在所有 Java 提交中击败了 88.07% 的用户 内存消耗： 37.5 MB , 在所有 Java 提交中击败了 82.19% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    // 1 2 7 8 9

    // 3 6 9 1

    class Solution {
        public int firstMissingPositive(int[] nums) {
            if(nums.length == 0){
                return 1;
            }
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i && nums[i] > 0 && nums[i] < nums.length) {
                    // 要是两个一样的，对换会变成死循环
                    if(nums[i] == nums[nums[i]]){
                        break;
                    }
                    swap(nums, i, nums[i]);
                }
            }
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == i) {
                    continue;
                } else {
                    return i;
                }
            }

            // 判断第0位 是不是等于数组长度
            if (nums[0] == nums.length) {
                return nums.length + 1;
            } else {
                return nums.length;
            }
        }

        private void swap(int[] nums, int a, int b) {
            int c = nums[a];
            nums[a] = nums[b];
            nums[b] = c;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] nums2 = new int[]{-1,3,4,5,6,1};
        Solution solution = new P41FirstMissingPositive().new Solution();
        System.out.println(solution.firstMissingPositive(nums2));
        // TO TEST
    }

}